ON VERIFICATION ALGORITHMS FOR SOME BINARY RELATIONS ON THE GENERAL
SUPERMONOID OF A FREE MONOID 

Mel'nikov Boris Feliksovich, Doctor of physical and mathematical sciences, professor, sub-department of information systems and networks, Russian State Social University (4 Wilgelma Pika street, Moscow, Russia), bf-melnikov@yandex.ru
Korabel'shhikova Svetlana Jur'evna, Candidate of physical and mathematical sciences, associate professor, sub-department of informatics and information security, Northern (Arctic) Federal University named after M. V. Lomonosov (17 Severnoy Dviny embankment, Arkhangelsk, Russia), s.korabelsschikova@narfu.ru
Churikova Nadezhda Petrovna, Postgraduate student, Samara NationalResearch University named after academician S. P. Korolyov (34 Moskovskoe highway, Samara, Russia), claorisel@gmail.com

512.53, 510.54

10.21685/2072-3040-2017-3-8

Background. The subjects of the study are free semigroups and special binary relations (free semigroup) defined on the global supermonoid of a free monoid. In this paper, we consider some special binary relations in languages (elements of the global supermonid), especially the so-called equivalence relation at infinity, which we considered in previous papers and which is an equivalence relation. We describe algorithmsfor verifying the fulfillment of these relations for elements of the global supermonoid of a free monoid. We also consider a special order relation on subsetsof a set of words that is given by a language that is minimal in this relation among all languages equivalent at infinity to the given one.
Material and methods. General methods of analysis and synthesis are used in this work. Special methods of the theory of formal languages, methods for describing algorithms and methods of working with semigroups are also used, in particular,the method of constructing a morphism of a semigroup.
Results. The article gives examples of constructing two languages (two elementsof a supermonoid) for which the equivalence relation we are considering is satisfiedin the supermonoid. The most important result of the paper is a description of the effectivealgorithm that answers the question whether the iterations of two given finitelanguages are equivalent at infinity. Algorithms and examples presented in the article are relevant for the application of special variants of the automated transformationof regular grammatical structures and context-free grammars in compiler building automation systems.
Conclusns. In many special cases, described by us in previous publications, the analogues of the considered algorithms are polynomial. However, in the generalcase, the question of the existence of polynomial algorithms that answer the questions posed in the article remains open.

formal languages, infinite languages, free monoid, supermonoid, iteration of language

1. Melnikov B. F. International Journal of Foundation of Computer Sciences. 1993, vol. 4, no. 3, pp. 267–273.
2. Mel'nikov B. F. Vestnik Moskovskogo universiteta. Ser. 15, Vychislitel'naya matematika i kibernetika [Bulletin of Moscow University. Series 15. Calculus mathematics and cybernetics]. 1996, no. 4, pp. 49–55.
3. Mel'nikov B. F. Izvestiya vysshikh uchebnykh zavedeniy. Matematika [University proceedings. Mathematics]. 2004, no. 3, pp. 46–56.
4. Alekseeva A. G., Mel'nikov B. F. Vektor nauki Tol'yattinskogo gosudarstvennogo universiteta [The vector of science of Togliatty State University]. 2011, no. 3, pp. 30–33.
5. Korabel'shchikova S. Yu., Mel'nikov B. F. Vestnik Severnogo (Arkticheskogo) federal'nogo universiteta. Ser.: Estestvennye nauki [Bulletin of Northern (Arctic) Federal University. Series: Natural Sciences]. 2016, no. 3, pp. 91–96.
6. Melnikov B. Number theoretic and algebraic methods in computer science. 1995, pp. 125–137.
7. Dang V. V., Korabel'shchikova S. Yu., Mel'nikov B. F. Izvestiya vysshikh uchebnykhzavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki [University proceedings. Volga region. Physical and mathematical sciences]. 2015, no. 3 (35), pp. 88–99. 8. Dubasova O. A., Mel'nikov B. F. Programmirovanie [Programming]. 1995, no. 6, pp. 46–57.
9. Melnikov B., Kashlakova E. Informatica (Lithuanian Acad. of Sciences). 2000, vol. 11, no. 4, pp. 441–446.
10. Baumgertner S. V., Mel'nikov B. F. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki [University proceedings. Volga region. Physical and mathematical sciences]. 2013, no. 2 (26). – S. 64–74.
11. Dolgov V. N., Mel'nikov B. F. Vestnik Voronezhskogo gosudarstvennogo universiteta. Ser.: Fizika. Matematika [Bulletin of Voronezh State University. Series: Physics. Mathematics]. 2013, no. 2, pp. 173–181.
12. Doglov V. N., Mel'nikov B. F. Vestnik Voronezhskogo gosudarstvennogo universiteta.Ser.: Fizika. Matematika [Bulletin of Voronezh State University. Series: Physics. Mathematics].2014, no. 1, pp. 78–85.
13. Zubova M. A., Mel'nikov B. F. Stokhasticheskaya optimizatsiya v informatike [Stochastic optimization in informatics]. 2015, vol. 11, no. 2, pp. 17–29.
14. Cohen R. S., Gold Y. J. Comp and System Sci. 1977, no. 15, pp. 169–184. 15. Mel'nikov B. F. Vestnik Moskovskogo universiteta. Ser. 15, Vychislitel'naya matematika i kibernetika [Bulletin of Moscow University. Series: Calculus mathematics and cybernetics].1991, no. 3, pp. 51–53.